1. Field of the Invention
This invention relates generally to computer systems and more particularly to a system and method for controlling computer processes in a multiprogramming/multiprocessing environment.
2. Description of the Prior Art
Electronic computers have grown from first generation hardware characterized mainly by vacuum tubes, to second generation hardware characterized by transistors, to third generation hardware characterized, in the main, by integrated circuits. Along with these different generations of hardware there were different generations of software, wherein first generation software was characterized mainly by machine language, assemblers and subroutines, and second generation software was characterized by high-level languages, monitors and macro assemblers. Third generation software is characterized by operating systems, on-line real-time systems multiprogramming systems, and data management systems.
The first generation hardware in combination with first generation software, and also the second generation hardware in combination with second generation software were primarily oriented toward batch processing where jobs were executed primarily in serial fashion. Moreover, the third generation of hardware software systems are also batch-process oriented; however because of the advent of multiprogramming, several jobs may be executed in parallel rather than serial, and permits the acceptance of input information for processing as it is generated.
The fourth generation system will be capable of satisfying the following requirements:
1. "The system will be classified as a communication and control system and will be capable of widely diversified processor applications. Intrasystem and intersystem communication interface will be required for both hardware and software. PA1 2. "The system will be controlled primarily by data rather than by programs as were previous machines: i.e., system control will be established primarily by input rather than by stored instructions. Development of this characteristic is dependent upon submission of information in real-time. Feedback is a key consideration. Proper interactions between intersystem and intrasystem interfaces is vital. The inter-relationships between data (communication bits) and programs (information bits) must be carefully defined. PA1 3. "Hardware will govern communication and control procedures; use of system control programs will be substantially reduced or eliminated. This characteristic is closely related to the preceding one. Focalizing system design by application of communication networks will eliminate much of the need for software and facilitate system control. Again, consideration of both intersystem and intrasystem data flow is important. When such techniques are applied, requirements for software control of the system will be minimized. PA1 4. "Most processing will be executed in real-time; operations will be performed on input at a rate that provides output within the required response time. Real time, as discussed here, does not imply interleaving of programs or the man-machine interaction of time sharing. Rather, the implication is that the system will accept data as it is made available and process this data within the constraints imposed by desired response times. PA1 5. "The system will be readily expandable. Hardware and software will be functionally modular in design. Computing power will be modified without redesign of the system. A variable instruction set is not implied. However, nested subsets of hardware will be available to complement nested subsets of software. In fact, this nesting of software is currently practiced. The user's software commonly includes both action macros and system macros. System macros commonly contain nested macros which perform communication functions for specified terminal devices. Such macros can be removed or specialized; system modularity results. Impetus is given to applying the family concept in the hardware (e.g. terminal) design." (Fourth Generation Computers: User Requirements and Transition; "The Significance of the Next Generation; Technical Keynote Presentation" by Dr. C. J. Walter and Arline Bohl Walter. Edited by Fred Gruenberger, Prentice-Hall Inc. Englewood Cliffs, N.J. 1970 pps. 16-17 by permission of the publisher).
37 Multiple shift registers, large low-cost read-only memories, and batch-fabricated multifunction semiconductor devices make new computer organization feasible. Logic elements will perform a variety of tasks. For example, steering flip-flops will identify specific operations. These flip-flops will be set by serial or serial-parallel insertion of bits onto a subset of the leads to each logic package and an appropriate combination of clock and control signals. Data will be directed to a storage element with a more general (or rapid) access to other points in the system. Self-reconfiguration techniques and variable control memory structures will be possible because of steering flip-flops which identify inputs as control data, operating information, or data to be manipulated. Thus, main memory or scratch pad memory will temporarily assume the functions of control memory in the computer. Reconfiguration of a computer organization on a seemingly instantaneous basis will be possible. Parallel processing will be readily performed.
Processing in first generation hardware-software computer systems was relatively straightforward where the job or program was considered the basic processing unit. For each user initiated job or transaction a program generally ran with little or no interruption until the job or transaction was completed. Many straightforward jobs such as the compilation and execution of a high level language program, such as FORTRAN, could and did run as a single process. More difficult jobs, however, would require multitask operations and they would create other processes as they ran. (Note that a process is a concept implying the carrying on of some activity and should not be confused with the concept of a program, which is an activity description and can be used by one or more processes. We can speak either of a process or a processor executing a program. See Glossary of Terms).
The concept of a process as being the basic processing unit developed to fill a need for the multiprogramming/multiprocessing environment of third generation computers. In such an environment where many users are demanding service simultaneously, it is natural to conceive of multiple processes competing for resources within the computer system. Each process consists of a program (i.e. an ordered collection of instructions and other data associated with the instructions) which is executed by the computer and operates on data to perform a user's job or some phase of that job. Where many such processes are demanding simultaneous attention from the system, the task of communicating with and between such processes and the task of controlling and allocating resources to such processes particularly in view of the requirements of fourth generation systems becomes extremely complex.
The Burroughs B-6500 and B-7500 computer, discussed in an article by E. A. Hauch and B. A. Dent entitled Burroughs B-6500/B-7500 Stack Mechanism, Proc. AFIPS Spring Joint Comp. Conf. 1968 pps. 245-251, Thomson, Washington, D.C. and also discussed in an article by J. G. Cleary entitled Process Handling on Burroughs B-6500 Proceedings of Fourth Australian Computer Conference, Adelaide, South Australia 1969, provides some measure of control of processes by utilizing a stack mechanism. Basically "each process is assigned memory for a stack in which are stored local variables, references to program procedures, data arrays and current process status . . . the stack operates as a last in first out storage area . . . an active process is represented by an active stack" (J. G. Cleary above pps. 231-232). Accordingly a stack has the facility for storing the dynamic history of a program under execution.
Cleary further describes (pps. 233-234) how simple "Stack Trees-or Cactus Stacks of the Saguaro type" may be created to provide a vehicle for the control of multiprogramming and parallel processing.
However the stack mechanism techniques disclosed in the article are not totally satisfactory for fourth generation computer systems mainly in that they do not provide for adequate protection of information by restricting access to information to the myriad other processes of such fourth generation system, in accordance to some privilege accorded each process.
A paper entitled "Process Control and Communication" by A. J. Bernstein, G. D. Detlefsen and R. H. Kerr published in ACM Second Symposium of Operating Systems Principles, 1969, pages 60-67, describes "the structure of processes and the interprocess communication facility implemented within a general purpose operating system.
This system allows a process to consist of up to four parts called its logical segments. These segments may be in physical disjoint locations when the process is in store. Relocation and protection of these segments is accomplished by four registers.
Generally the processes are controlled by an operating system which implements primitives (i.e. pseudo instructions) issued by the process and utilizing a mechanism by which the processes communicate with one another. Primarily communication comprises sharing events the same way they may share a file. Each process has KIT (Known Items Table) entries pointing to the same AIT (Active Items Table) entry which contains a unique entry for each currently open file. By means of this structure one process may request notification (by issuing a NOTIFY primitive) when the event occurs. As a result the operating system creates an entry on an event queue associated with the event which identifies the requesting process awaiting notification. At this point the requesting process may continue execution or it may suspend itself by issuing a BLOCK primitive. The event is said to occur when some other process issues a CAUSE primitive to it and can be catalogued and treated in the direction structure using the same primitives. Information may then be transferred from one process to the other or the processes otherwise cooperate to perform a given task. Other primitives in the operating system create and spawn processes or destroy them.
This technique of process communication and control does not provide an orderly dynamic history of the program under execution, but does introduce some concepts of software multiplexing of processes and event management. Nor does this technique provide for protection of one process from another by levels of privilege. Nor does it provide for an efficient manner of passing messages from one process to another. Moreover addressing processes and relocation appears inadequate for fourth generation systems. What is needed for fourth generation systems is a firmware/hardware system which efficiently addresses and relocates processes, and provides information structures identifying the state of the process and further supporting the process for controlling these states and for protection from other processes and from themselves by levels of privilege and which efficiently dispatches processes and synchronizes with other processes, and permits users who have written their programs in a modular way to pass from one program module to the other.
These and other requirements and their attendent problems in devising computer systems that effectively perform the required functions, with some suggestions for achieving some of these functions are discussed in a paper by Butler W. Lampson entitled "A Scheduling Philosophy for Multiprocessing Systems" published in ACM11 (5) Association for Computing Machinery Vol. 11, No. 5, May, 1968. However, the suggestions discussed in this article do not appear to solve the problems.
In a multiprogramming/multiprocessing environment, it is essential that cooperation between two or more sequential processes be efficiently and expeditiously realized. While many solutions to this problem have been proposed in the past, the technique of process communication and control needed for the fourth generation computers has not, until now, been fully realized. The germination of the concepts required for a fourth generation computer, however, have been partially developed by E. W. Dijkstra in a paper entitled "Cooperative Sequential Processes from Programming Languages", NATO Advanced Study Institute, edited by F. Genuys of Paris and published in Academic Press, 1968. In this paper, Dijkstra postulates a basic concept of a semaphore for use in process synchronization and P and V instructions operating upon the semaphore. Unfortunately, Dijkstra provides for process communication and process synchronization solely by software usage thus not only slowing down the operating time of the system but also decreasing the efficiency and overall overhead required for such a system. More importantly, Dijkstra does not provide the concepts required for any significant exploitation of a fourth generation computer since he formulates only a basic premise in process synchronization. For example, the transmission of messages from one process to another is not anticipated nor explained in Dijkstra's paper. What is required for the fourth generation is a system which automatically integrates process communication and process control so as to not only enhance the operating efficiency of the system but also to provide sufficient flexibility to deal with the numerous situations arising in the transfer of information from one process to another.
The concepts of P and V instructions has been previously expounded by Edsger W. Dijkstra in the previously cited article. However, these concepts are presented only in generalized terms and do not provide the system configuration needed in a fourth generation computer. Moreover, Dijkstra merely provides a software basis for interpreting and using P and V instructions. Thus the memory organization necessary for rapidly accessing processes in addition to providing a systematic reallocation of the data processor has not been contemplated. As a result, not only are many of the P and V instructions necessary for delivering or receiving data by the executing processes not shown by Dijkstra but also the hardware/firmware basis for enabling process transferral in response to all P and V instructions is not envisioned.